# -*- coding: utf-8 -*-            
# @Time : 2023/8/6 16:03
# @Author  : lining
# @FileName: 给定中序，后序，还原二叉树.py
"""
                1
          2          3
      4      5    6     7
先序1，2，4，5，3，6，7
中序4，2，5，1，6，3，7
后序4，5，2，6，7，3，1
要先做右子树遍历，因为先取到右子树节点
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
"""


class Node():
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def solution(postorder, inorder):
    """
    postorder:后序
    inorder:中序
    """
    if not postorder:
        return
    if not inorder:
        return
    if len(inorder) == 1:
        postorder.remove(inorder[0])
        return Node(inorder[0])
    root = Node()
    root.value = postorder[-1]
    del postorder[-1]
    for a, b in enumerate(inorder):
        if b == root.value:
            root.right = solution(postorder, inorder[a + 1:])
            root.left = solution(postorder, inorder[0: a])
            return root


# postorder = [4,5,2,6,7,3,1]
# inorder = [4,2,5,1,6,3,7]
inorder = [9, 3, 15, 20, 7]
postorder = [9, 15, 7, 20, 3]
x = solution(postorder, inorder)
print(x)
